A typical multiprocessing computer system has the capability to perform several tasks in parallel. However, some mechanism must be used to synchronize these parallel processes so that invalid results or race conditions do not occur. Traditionally, semaphores have been used to satisfy this synchronization requirement. The traditional semaphore known to those of skill in the art consists of a count, a limit, and a queue for tasks to wait on. Two types of semaphore instructions are required for normal operation. A "V" type of semaphore instruction is used by a "producer" process when it has produced information for use by a "consumer" process. A "P" type of semaphore instruction is used by a "consumer" process when it requests information produced by a "producer" process. The "P" operation is used to enter mutual exclusion, while the "V" operation is used to exit mutual exclusion. The traditional semaphore is described in more detail in "Structured Computer Organization" by Andrew Tanenbaum, Section 5.33, incorporated herein by reference. U.S. Pat. No. 4,320,451 also describes the semaphore and is also incorporated herein by reference.
An analogy of the semaphore operation is helpful to explain its operation. Imagine it is Halloween, it is just getting dark, and Harry the Homeowner has just filled up a candy dish with 3 pieces of candy. The candy dish is just big enough for 3 pieces of candy. Harry doesn't want to be bothered by trick or treaters all night, so he leaves the candy dish out on the porch next to the porch swing with a sign that says the following: "Take one piece of candy from the candy dish. If the candy is all gone, you may sit on the porch swing and wait for the dish to be refilled if you want to." At the start of the evening, all 3 pieces of candy are available to be consumed (count=3) and are stored in the candy dish (limit=3). Each of the trick or treaters (processes) is capable of taking a piece of candy from the candy dish (consumer process) independent of the actions of the other trick or treaters (multiprocessing system). Harry is capable of refilling the candy dish with more candy (producer process).
When the first trick or treater wants a piece of candy, he takes one from the candy dish (consumer process). There are now two pieces of candy available (count=2). When 2 more trick or treaters want a piece of candy, they each take one from the candy dish. Now there are 0 pieces of candy available (count=0). If a 4th trick or treater wants a piece of candy, he cannot get one (since count=0) until Harry adds a piece of candy to the candy dish (incrementing the count to 1). If this fourth trick or treater can wait, he sits down on the porch swing and waits for Harry to refill the candy dish (count=-1 indicating one trick or treater waiting for a piece of candy). When Harry adds another piece of candy to the candy dish the waiting trick or treater takes it (count incremented to 0). If this fourth trick or treater cannot wait, he dejectedly moves on to the next house (consumer request fails).
Harry thought that putting the candy dish out on the porch would give him some peace and quiet on Halloween, but he finds himself running out to the porch every few minutes to refill the candy dish. Harry figures out that he could be much more efficient if he could put some extra candy down in the porch swing next to the candy dish, where it would wait for the next trick or treater to take a piece of candy (count=4 indicating one piece of candy waiting for a trick or treater). Harry is told by the Halloween Advisory Commission that he cannot do this, because the rules do not allow it.
The above analogy shows one of the problems with the traditional semaphore architecture. Because the count cannot exceed the limit, "V" type semaphore instructions fail if the count is equal to the limit. Therefore a "producer" process cannot wait for a "consumer" process if the count is equal to the limit. This failure makes the "V" type semaphore instruction asymmetrical with the "P" type instruction, which permits a consumer process to wait for a producer process. This asymmetrical nature between the P and V instructions means that both are necessary in a normal multiprocessing environment. This requirement complicates the operational interface between the semaphore and the processors of the multiprocessing system.